/*
给定一个人坐过的一些飞机的起止机场，已知这个人从 JFK 起飞，那么这个人是按什么顺序
飞的；如果存在多种可能性，返回字母序最小的那种

输入输出样例
	输入是一个二维字符串数组，表示多个起止机场对子；输出是一个一维字符串数组，表示飞
行顺序

Input: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Output: ["JFK", "MUC", "LHR", "SFO", "SJC"]

*/
vector<string> findItinerary(vector<vector<string>>& tickets) {
	vector<string> ans;
	if (tickets.empty()) {
		return ans;
	}
	unordered_map<string, multiset<string>> hash;
	for (const auto & ticket : tickets) {
		hash[ticket[0]].insert(ticket[1]);
	}
	stack<string> s;
	s.push("JFK");
	while (!s.empty()) {
		string next = s.top();
		if (hash[next].empty()) {
			ans.push_back(next);
			s.pop();
		}
		else {
			s.push(*hash[next].begin());
			hash[next].erase(hash[next].begin());
		}
	}
	reverse(ans.begin(), ans.end());
	return ans;
}
